package zw_501_600.zw_506_相对名次;

import java.util.Arrays;

class Solution {

    public static void main(String[] args) {
        int[] score = {10, 3, 8, 9, 4};
        String[] ranks = findRelativeRanks(score);
        for (String rank : ranks) {
            System.out.print(rank + " ");
        }
    }

    /**
     * 方法一：排序
     * 题目要求找到每个运动员的相对名次，并同时给前三名标记为"Gold Medal", "Silver Medal", "Bronze Medal"，其余的运动员则标记为其相对名次。
     * 将所有的运动员按照成绩的高低进行排序，然后将按照名次进行标记即可。
     * 时间复杂度：O(nlogn)，其中 n 为数组的长度。我们需要对数组进行一次排序，因此时间复杂度为 O(nlogn)。
     * 空间复杂度：O(n)，其中 n 为数组的长度。
     *
     * @param score
     * @return
     */
    public static String[] findRelativeRanks(int[] score) {
        int n = score.length;
        String[] desc = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = score[i];
            arr[i][1] = i;
        }
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        String[] ans = new String[n];
        for (int i = 0; i < n; ++i) {
            if (i >= 3) {
                ans[arr[i][1]] = Integer.toString(i + 1);
            } else {
                ans[arr[i][1]] = desc[i];
            }
        }
        return ans;
    }

//    public static String[] findRelativeRanks(int[] score) {
//        int len = score.length;
//        int[] nums = score.clone();
//        Arrays.sort(nums);
//        String[] str = {"Gold Medal", "Silver Medal", "Bronze Medal"};
//        String[] ans = new String[len];
//        for (int i = len - 1; i >= 0; i--) {
//            for (int j = 0; j < len; j++) {
//                if (nums[i] == score[j]) {
//                    if ((len - i - 1) < 3) ans[j] = str[len - 1 - i];
//                    else ans[j] = String.valueOf(len - i);
//                    break;
//                }
//            }
//        }
//        return ans;
//    }
}
